기술노트 : 희소행렬.
컴퓨팅에서 꽤 중요한 개념인데, 나는 이것을 최근에야 주워들었다. 뭐 희소행렬에 대해 잘 안다는 것은 아니고 개념만 읽었다.
빅데이터 분야에서는 특히 희소행렬 형태의 데이터가 많이 출현하므로, 새로운 자료구조 또는 물리적 메모리 구조가 출현했으면 한다. 자료구조나 파일 시스템 처리 모델 자체는 지금도 있을 것이다. 다만 물리적으로 정확히 데디케이트 된 메모리 제품은 없는 것으로 안다. 물리적인 새로운 형태의 메모리나 스토리지 유형이 필요한 이유는 이렇다.
속도와 크기면에서 큰 향상을 가져올 수 있기 때문이다.
실은 나도 이 문제 때문에 고민을 해본 적 있고, 여튼 효율적으로 다뤄보겠다고 구현을 한 적이 있다. 아마도 python pandas나 기타 수학용 라이브러리, 스파크에서는 기본적으로 지원하리라. 예컨데 ALS나 팩토라이즈 머신의 주 대상은 희소행렬일 것이다.
나의 고민은 이러했다. 대부분이 0으로 비어있는 2차원 배열이다. 그런데 각 벡터의 길이가 들쭉날쭉하여 정방형은 아니다. (단일 벡터의 최대 길이의 끝까지 0으로 채운다면 정방형으로 봐도 무방할 것이다.)
이제 n * n 번 계산을 수행하는데, 추천기 연산 등은 사실 n * n * n이다. 대부분이 0이므로 싱글 머신 컴퓨팅에서는 메모리 낭비가 걱정이 된다. 천만개 아이템을 계산하는데는 문제가 없지만 1억개라면 64기가 정도의 메모리 사이즈를 갖는 컴퓨터로는 그냥 메모리에 담을 수가 없다. mmap을 디스크에 사상해서 사용할 수도 있지만 이렇게 되면 이제 속도가 문제가 된다. 이런 연산을 싱글 머신의 메모리 연산으로 전환한 이유는 분산 컴퓨팅보다 빠르게 하기 위함인데, 느려서는 그냥 하나마나다. 왜 분산 컴퓨팅을 안 했냐에 대해서는 다른 문제이므로 추후 다룬다.
그렇다면 벡터(배열)을 안 쓰고 그냥 리스트를 쓰는 것이 합리적이라고 생각할 수 있다. 나의 경우 즐겨쓰는 rb-tree를 이용했다. 그런데, 이러면 검색 비용이 든다. 더욱 더 치명적인 문제는 캐시를 못 탄다는 것이다. 캐시를 못 탈 뿐만 아니라 빈번한 분기로 인해 파이프도 수시로 깨질 것이다. 성능상 최악이다.
이미 알려져 있는 방법은 잘 모르겠지만서도.. 어쨌든 내가 취한 방법은 이렇다. 벡터에 삽입시 인덱스:값으로 차곡차곡 쟁여서 저장한다. 그리고 이 벡터는 정렬해 둔다. 퀵소트는 캐쉬를 태우므로 비용이 생각보다 적다. 대부분이 0인 희소 행렬이기 때문에 정렬 비용은 더욱 작다. 그 다음 n * n 의 연산을 수행할 때 인덱스를 이용하여 인덱스가 없는, 즉 벡터상 없는 요소는 건너뛴다. 이러면 루프를 이용하여 두 열의 연산을 수행할 수 있으며 벡터는 메모리의 로캘리티가 유지되기 때문에 캐시도 탄다. 성능은 비교할 수 없이 빠르다.
희소행렬을 위한 메모리가 출연한다면 아마도 이런 스펙을 갖춰야 한다.